Cell phone text messaging is a huge business worldwide, with many messages sent and received each year. Text messages are a convenience for the sender and the receiver. The sender can send the message silently and quickly, without worrying about having to play “phone tag” or risking interrupting someone with a phone call while they are driving or when they are in a meeting. The receiver can generally read the message at a glance and obtain important information in a silent, unobtrusive manner.
Text message services that allow groups of people to coordinate with one another via their cell phone and text messaging are becoming more widely available. The popularity of text messaging is likely to grow exponentially in the coming years as people discover how useful it can be. Text messaging is particularly helpful for people in a business environment who travel a lot and need to coordinate activities. For example, text messaging is particularly useful for government and nongovernmental agencies working together for disaster relief for purpose of coordinating their activities.
Cell phone text messaging is also a useful technique for allowing deaf people to communicate with their business associates, friends, and families. While it might seem counterintuitive for deaf people to carry cell phones, they can benefit greatly from being able to communicate through text messaging.
The currently popular systems used today for text entry on a cell phone, such as multi-tap and T9, have a number of disadvantages. The multi-tap approach, which involves a click, double-click, triple-click or even a quadruple-click of a key to indicate which letter on the key is intended by the user, involves two primary disadvantages: one is the excessive quantity of keystrokes for a given word and the other is the need for a timeout period between letters. So, for example, if you are entering the word “bars”, then “2,2,<pause for timeout>” is entered for “b”, then “2” is entered for “a”, then “7,7,7<pause for timeout>” is entered for “r”, then “7,7,7,7” is entered for “s”—a total of 10 key presses and two timeouts for a four-character word. An inexperienced user may think that he needs to wait for the timeout to expire with every key pressed, rather than just for the ones where two adjacent letters in a word both happen to fall on the same key. Thus, an inexperienced user might experience one timeout per key pressed. An experienced user would “barge” through the timeout when clicking a variety of keys, but he or she would have to consciously think about when the timeout period can be ignored and when it can't. The mental processing associated with determining whether or not to ignore the timeout interferes with the thought process involved in composing a message and causes some level of irritation in the user.
The T9 system (and others like it) involves words appearing on the display that are statistically likely to match the word being typed as the person taps one key per letter, but these words may or may not actually be the word intended by the user. Thus, you may be trying to send a message that your cat is stuck in a tree, but when you type the word “cat”, the system may present “act” or “bat”—two other words that might match. When you are composing a message, your concentration may be challenged when words appear that are unrelated to the word you intend. The mental processing associated with trying to ignore the irrelevant words interferes with the thought process involved in composing a message and also causes irritation.
Other systems have been devised that allow the user to type a word on a one key per letter basis and to perform the disambiguation on a letter-by-letter basis. This type of data entry is easier, because it allows you to focus on your message and to only think about disambiguation when the need actually arises to provide a correction. For example, the Dennis Connolly/David H. Lundy patents (U.S. Pat. Nos. 6,346,894 and 6,005,495) discuss “a method and system for intelligent text entry on a keypad . . . ” where the “application predicts which character of those corresponding to that key is [the character] intended by the user” and the user has an opportunity to select that letter or else cycle through the other letters on that same key in order to pick the one that is needed. These patents describe the idea of using sequences of letters (4-grams, n-grams) and their relative frequencies to determine the next most likely letter in relation to the pressing of a given key. They also describe the idea that the position of a word in relation to other words (verbs, prepositions, nouns, etc.) within a sentence can help determine the probability of the next word.
Unfortunately, the 4-gram approach alone does not provide as sophisticated an algorithm as may be needed in order to make the one-key-per-letter system as user-friendly and effective as possible. Furthermore, any system that provides statistical analysis of sequences of words (verbs, prepositions, nouns, etc.) is likely to be resource-intensive in terms of memory, data storage space and processing.
Below are examples of situations in which the 4-gram/n-gram approach can fail. The number “6” appears where an “m”, “n” or “o” might be intended by the user after having already entered a number of letters.
Some examples include affecti6_: n or o (affecting/affection) and bisecti6_: n or o (bisecting/bisection); ambiti6_: o (ambition) and biti613 : n (biting); attracti6_: n or o (attracting/attraction) and acti6_: n or o (acting/action); eati6_: n (eating) and creati6_: n or o (creating or creation)
It can be observed from the examples above that knowing the four or even five letters that precede a given keystroke will not necessarily allow a computer program to be able to guess with certainty what the expected next character should be. In some cases knowing the entire first portion of the word helps, whereas in other cases the computer just has to make a statistically-based guess, because even then more than one word matches the entire first portion of the word.
The computer program can usually guess better when it matches a dataset with the entire first portion of the word that has been entered so far by the user. However, storing the entire word for all words in a given dictionary is expensive in terms of disk space, memory and processing time. A better approach is a hybrid approach in which a letter-position “multi-gram approach” is used for most situations and the word match approach is used for the more difficult words.
Depending upon the memory and storage of a given device, the letter-position “multi-gram approach” could use digrams for the majority of its letter predictions, and trigrams, 4-grams or longer letter sequences (also known as multi-grams) for the more ambiguous words.
The lists of words containing two-letter digrams below illustrate the concept that digrams have a variety of important positional and frequency characteristics in relation to words in a given language. In a manuscript, such as a novel, some digrams such as “er” are found in a high percentage of words and others are found in a very low percentage of words. Some of the words containing a given digram may be high-frequency words, such as “and” or “the,” whereas others may be low frequency words, such as “aardvark.” Some digrams are typically found at the beginning of a word, whereas others are typically found near the end, and others are sprinkled fairly evenly throughout the words in a text sample. The positioning of “cc” within a word is typically at the second and third letters (e.g., “accept”) and sometimes at the third and forth letters (e.g., “success”). The listing below illustrates that positioning of “ff” within commonly-used words is very similar to the positioning of “cc”. The positioning of “lu” is more likely to be toward the beginning or the middle of a word than at the end of a word. The letters “ou” are rarely found past the tenth letter of a word. Of course, letter sequences such as “es”, “ing”, “ly”, “tion”, “sion” and “ed” are often found at the end of a word. A disambiguation approach that uses this type of valuable digram-position information will be more successful than one that does not. The same point is also true of the positioning of trigrams, 4-grams or longer-length strings of letters.
Words that have a double “c” (such as cc) include accept, acceptable, accepted, accepting, accepts, accessible, accompany, accompany, according, account, accounted, accounts, accurate, accurately, accustomed, occasion, occasionally, occasions, occupied, succeed, succeeded, success, successful, and successfully.
Words that have a double “f” (such as ff) include affably, affected, affection, affirmative, affluence, afford, afforded, difference, different, difficulty, effect, effort, ineffectually, longsuffering, muff, muffle, muffled, off, offered, office, offices, official, officials, officiate, officiates, ruffled, ruffled, ruffles, ruffling, suffer, and sufficient.
Words that have an “lu” include absolute, absolutely, affluence, bluntly, blustering, clump, conclusive, delusion, failures, flung, flushed, flushed, including, luckless, ludicrous, ludicrously, luminous, lunch, luxuriant, luxurious, luxurious, luxuriously, luxury, luxury, luxury, reluctantly, resolute, resolutely, resolution, and volunteered.
Words that have an “ou” include about, account, accounted, accounting, accounts, ambitious, ambitiously, anxious, around, boundary, bounties, bountiful, bounty, brought, cautiously, commodious, confoundedly, contemptuously, cough, could, couldn't, counselors, course, courts, cousin, curiously, doubt, doubted, doubtfully, doubts, encounter, encountered, encountering, encounters, enough, enviously, espouse, fastidious, found, four, ground, grounds, hour, house, imperiously, incautiously, judicious, loud, louder, loudest, loudly, ludicrous, ludicrously, luminous, luxurious, luxuriously, malicious, mournfully, mouth, nouns, ominous, ominously, ought, our, out, outdoors, outside, playground, pour, profound, pronounced, proud, proudest, proudly, rapacious, rebellious, redoubtable, redoubtable, rough, roughly, round, should, shoulder, shoulders, soup, spacious, superstitious, tenacious, thorough, though, thought, thoughtfully, thoughts, thousands, through, touched, trouble, troubled, troubles, undoubtedly, victorious, vigorous, vigorously, virtuous, without, would, you, young, your, yours, yourself, and youth.
It is possible to perform statistical studies of words found in manuscripts of a given language using a computer program and to store the results in a format that another computer program can utilize via a decision tree, probability table or equivalent method in order to make predictions about what letter would typically follow the previously typed letters of a word. Then, as the user clicks on a given key on a reduced keypad (e.g., “2-ABC”, “3-DEF”, “4-GHI”, “5-JKL”, “6-MNO”, “7-PQRS”, “8-TUW”, and “9-WXYZ”), the program can display the next likeliest letter.
Cell phones are limited in their computer memory, and thus designers of programs for cell phones are interested in finding ways to make their programs compact. A trade-off must be made between the desire for a compact disambiguation program and one that has the maximum possible level of effectiveness. Generally speaking, a 4-gram model would be less compact but more effective than a trigram model, and a trigram model would be less compact but more effective than a digram model. However, for purposes of trying to satisfy the programmatic goals of compact size and maximum effectiveness, a system can be devised that uses 4-grams (or even long portions of words) for particularly ambiguous sequences, trigrams for other sequences, and digrams for all of the rest. This approach can be described as a “multi-gram approach.” The “multi-gram approach” is defined as the programming approach that uses statistical or empirical studies to determine the best combination of digrams, trigrams, 4-grams, long portions of words, etc., to meet the twin goals of compact program size and maximum program effectiveness. Thus, a “multi-gram” is a digram, trigram, 4-gram, n-gram or word portion that is used by an optimized program for the purpose of determining the most likely next character desired by a user when a multi-character key such as (“2-ABC”) is pressed.
All of the foregoing paragraphs have discussed the technique of disambiguation in relation to pressing keys on a keypad. Another technique for adding words to messages could also be used in conjunction with pressing keys: voice recognition. According to the March 1988 edition of the Atlantic, 43 words account for half of the words that are used in normal conversation. Voice recognition works best with limited sets of words, particularly when used in a variety of environments (e.g., while on the sidewalk, in a car, in an office, in a restaurant, etc.). So, an optional feature for adding words to messages could be voice recognition of certain frequently-used words but not infrequently-used words. Such a device could have a default list of frequently-used words as well as an extra list of user-entered words. So, for example, if a particular college student frequently invites his friends over for pizza, then he could add “pizza” to his list of spoken words to be recognized. Thus, the user who wanted to employ this optional feature would alternate between keyed entry of words and voice recognition of words.
It would be desirable therefore to provide a method and apparatus that more reliably predicts a letter when a key is pressed that has two or more letters assigned thereto.